数据结构作业 4、二叉树基础

2-1

树最适合于用来表示

A.

有序数据元素

B.

无序数据元素

C.

元素之间无联系的数据

D.

元素之间具有分支层次关系的数据

| 参考答案

答案

D

4分

2-2

一棵树有 $n_1$ 个孩子数为1的结点， $n_2$ 个孩子数为2的结点，……， $n_m$ 个孩子数为 $m$ 的结点，则该树的叶结点数为：

A.

$1+\sum^{m}_{i=2}(i)n_i$

B.

$\sum^{m}_{i=2}(i-1)n_i$

C.

$1+\sum^{m}_{i=2}(i-1)n_i$

D.

$1+\sum^{m-1}_{i=1}(i-1)n_i$

| 参考答案

答案

C

4分

2-3

如果A和B都是二叉树的叶结点，那么下面判断中哪个是对的？

A.

存在一种二叉树结构，其前序遍历结果是…A…B…，而中序遍历结果是…B…A…

B.

存在一种二叉树结构，其中序遍历结果是…A…B…，而后序遍历结果是…B…A…

C.

存在一种二叉树结构，其前序遍历结果是…A…B…，而后序遍历结果是…B…A…

D.

以上三种都是错的

| 参考答案

答案

D

4分

2-4

设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是

A.

n在m左方

B.

n在m右方

C.

n是m祖先

D.

n是m子孙

| 参考答案

答案

A

4分

2-5

设高为 $h$ 的二叉树（规定叶子结点的高度为1）只有度为0和2的结点，则此类二叉树的最少结点数和最多结点数分别为：

A.

$2h$ , $2^h-1$

B.

$2h-1$ , $2^h-1$

C.

$2h-1$ , $2^{h-1}-1$

D.

$2^{h-1}+1$ , $2^h-1$

| 参考答案

答案

B

4分

2-6

在下述结论中，正确的是：

①只有一个结点的二叉树的度为0;

②二叉树的度为2；

③二叉树的左右子树可任意交换；

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.

①④

B.

②④

C.

①②③

D.

②③④

| 参考答案

答案

A

4分

2-7

任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序

A.

发生改变

B.

不发生改变

C.

不能确定

D.

以上都不对

| 参考答案

答案

B

4分

2-8

二叉树中第5层（根的层号为1）上的结点个数最多为：

A.

8

B.

15

C.

16

D.

32

| 参考答案

答案

C

4分

2-9

二叉树的形态

由 3 个结点可以构造出 ▁▁▁▁▁ 种不同形态的二叉树。

A.

2

B.

3

C.

4

D.

5

| 参考答案

答案

D

4分

2-10

一棵非空二叉树，若先序遍历与中序遍历的序列相同，则该二叉树 ▁▁▁▁▁ 。

A.

所有结点均无左孩子

B.

所有结点均无右孩子

C.

只有一个叶子结点

D.

为任意二叉树

| 参考答案

答案

A

4分

2-11

一棵非空二叉树，若后序遍历与中序遍历的序列相同，则该二叉树 ▁▁▁▁▁ 。

A.

所有结点均无左孩子

B.

所有结点均无右孩子

C.

只有一个叶子结点

D.

为任意二叉树

| 参考答案

答案

B

4分

2-12

一棵有 1001 个结点的完全二叉树，其叶子结点数为 ▁▁▁▁▁ 。

A.

250

B.

254

C.

500

D.

501

| 参考答案

答案

D

4分

2-13

二叉树的高度

若根节点为高度1，一棵具有 1025 个结点的二叉树的高度为 ▁▁▁▁▁ 。

A.

10

B.

11

C.

11～1025 之间

D.

10～1024 之间

| 参考答案

答案

C

4分

2-14

一棵度为 4 的树中有 20 个度为 4 的结点、10 个度为 3 的结点、1 个度为 2 的结点和 10 个度为1 的结点，则树的叶子结点数为 ▁▁▁▁▁ 。

A.

41

B.

82

C.

113

D.

122

| 参考答案

答案

B

4分

2-15

一棵二叉树中有7个度为2的结点和5个度为1的结点，其总共有（）个结点。

A.

16

B.

18

C.

20

D.

30

| 参考答案

答案

C

4分

2-16

已知一棵二叉树的前序遍历结果为ABCDEFG,中序遍历结果为BCAEDGF,则后序遍历的结果为（）。

A.

CBAEGFD

B.

CBEGFDA

C.

BCEGFDA

D.

CBEFGDA

| 参考答案

答案

B

4分

2-17

深度为5的二叉树至多有（）个节点

A.

16

B.

32

C.

31

D.

10

| 参考答案

答案

C

4分

2-18

一个具有1025个节点的二叉树的高h为（）

A.

11

B.

10

C.

11～1025

D.

12～1024

| 参考答案

答案

C

4分

2-19

一棵高度为8的完全二叉树至少有（）叶子节点

A.

63

B.

64

C.

127

D.

128

| 参考答案

答案

B

4分

2-20

一棵满二叉树中127个节点，其中叶子节点的个数是（）

A.

63

B.

64

C.

65

D.

不确定

| 参考答案

答案

B

4分

2-21

某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）

A.

空或只有一个节点

B.

完全二叉树

C.

二叉排序树

D.

高度等于其节点数

| 参考答案

答案

D

4分

2-22

对一棵二叉树的结点从 1 开始顺序编号。要求每个结点的编号都大于其子树所有结点的编号，且左子树所有结点的编号都小于右子树所有结点的编号。可采用 ▁▁▁▁▁ 实现编号。

A.

先序遍历

B.

后序遍历

C.

中序遍历

D.

层次遍历

| 参考答案

答案

B

4分

2-23

对一棵二叉树的结点从 1 开始顺序编号。要求每个结点的编号都小于其子树所有结点的编号，且左子树所有结点的编号都小于右子树所有结点的编号。可采用 ▁▁▁▁▁ 实现编号。

A.

先序遍历

B.

后序遍历

C.

中序遍历

D.

层次遍历

| 参考答案

答案

A

4分

2-24

对一棵二叉树的结点从 1 开始顺序编号。要求每个结点的编号大于其左子树所有结点的编号、但小于右子树中所有结点的编号。可采用 ▁▁▁▁▁ 实现编号。

A.

先序遍历

B.

后序遍历

C.

中序遍历

D.

层次遍历

| 参考答案

答案

C

4分

2-25

已知一棵二叉树的先序遍历结果是ABC，则以下哪个序列是不可能的中序遍历结果：

A.

ABC

B.

BAC

C.

CBA

D.

CAB

| 参考答案

答案

D

4分